package com.springchang.leetcode.array;

/**
 * 第3题:将数组和减半的最少操作次数
 * <p>
 * 给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
 *
 * 请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
 * </p>
 * @TODO 没有通过全部测试用例，超时
 */
public class MinimumOperationsToHalveArraySum {

    public static int halveArray(int[] sourceNums) {
        double[] nums = new double[sourceNums.length];
        //遍历一遍，算出数组总和
        double sum = 0;

        for (int i = 0; i < sourceNums.length; i++) {
            nums[i] = sourceNums[i];
            sum += sourceNums[i];
        }

        //需要减掉的总数
        double target = sum/2.0;
        //已经减掉的总和
        double targetSum = 0;
        int count = 0;

        while(targetSum < target) {
            double maxNumber = 0;
            int index = 0;
            for (int i = 0; i < nums.length; i++) {
                if (targetSum + nums[i] / 2 >= target) {
                    index = i;
                    break;
                } else if (nums[i] > maxNumber) {
                    maxNumber = nums[i];
                    index = i;
                }
            }
            count++;
            targetSum += nums[index]/2;
            nums[index] /= 2;
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,19,8,1};
//        int[] nums = new int[]{3, 8, 20};
        System.out.println(halveArray(nums));
    }
}
